package per.hnvcam.common.impl;

import java.util.*;

import per.hnvcam.common.OrderedSet;

public class OrderedSetImpl<T> implements OrderedSet<T> {
   private List<T> elements;
   private Map<T, Integer> positions;
   private Comparator<T> comparator;
   private boolean isAscending;

   public OrderedSetImpl() {
      elements = new ArrayList<T>();
      positions = new HashMap<T, Integer>();
      isAscending = true;
      comparator = new PositionComparator();
   }

   public OrderedSetImpl(Collection<T> orderedCollection) {
      this();
      for (T item : orderedCollection) {
         add(item);
      }
   }

   public OrderedSetImpl(Comparator<T> comparator) {
      this();
      this.comparator = comparator;
   }

   @Override
   public boolean add(T item) {
      if (elements.contains(item)) {
         return false;
      }
      int position = getPositionOf(item);
      elements.add(position, item);
      updatePositions(position);
      return true;
   }

   private int getPositionOf(T item) {
      if (isEmpty()) {
         return 0;
      }
      int start = 0;
      int end = size() - 1;
      while (true) {
         if (start >= end) {
            return start + (comparator().compare(item, getAt(start)) > 0 ? 1 : 0);
         }
         int middlePos = start + (end - start) / 2;
         T middleItem = getAt(middlePos);
         int ordered = comparator().compare(item, middleItem);
         if (ordered == 0) {
            return middlePos;
         }
         else {
            start = ordered > 0 ? middlePos + 1 : start;
            end = ordered > 0 ? end : middlePos - 1;
         }
      }
   }

   @Override
   public boolean containsAll(Collection<?> objects) {
      throw new UnsupportedOperationException();
   }

   @Override
   public boolean addAll(Collection<? extends T> ts) {
      for (T item : ts) {
         add(item);
      }
      return true;
   }

   @Override
   public boolean removeAll(Collection<?> objects) {
      throw new UnsupportedOperationException();
   }

   @Override
   public boolean retainAll(Collection<?> objects) {
      throw new UnsupportedOperationException();
   }

   @Override
   public void clear() {
      elements.clear();
      positions.clear();
      isAscending = true;
   }

   @SuppressWarnings("unchecked")
   @Override
   public boolean remove(Object item) {
      int pos = -1;
      try {
         pos = indexOf((T) item);
      } catch (ClassCastException e) {
         pos = -1;
      }
      if (pos < 0) {
         return false;
      }
      return removeAt(pos) != null;
   }

   @Override
   public T removeAt(int position) {
      T item = elements.remove(position);
      positions.remove(item);
      updatePositions(position);
      return item;
   }

   private void updatePositions(int position) {
      for (int i = position; i < elements.size(); i++) {
         T movedItem = elements.get(i);
         positions.put(movedItem, i);
      }
   }

   @Override
   public int indexOf(T item) {
      Integer pos = positions.get(item);
      if (pos == null) {
         return -1;
      }
      return pos.intValue();
   }

   @Override
   public boolean isEmpty() {
      return elements.isEmpty();
   }

   @Override
   public boolean contains(Object o) {
      return positions.containsKey(o);
   }

   @Override
   public int size() {
      return elements.size();
   }

   @Override
   public T getAt(int position) {
      return elements.get(position);
   }

   @Override
   public void setAscendingSort(boolean isAscending) {
      this.isAscending = isAscending;
   }

   @Override
   public boolean isAscendingSort() {
      return isAscending;
   }

   @Override
   public Iterator<T> iterator() {
      return new OrderedSetIteratorImpl();
   }

   @Override
   public Object[] toArray() {
      return elements.toArray();
   }

   @SuppressWarnings("hiding")
   @Override
   public <T> T[] toArray(T[] ts) {
      return elements.toArray(ts);
   }

   @Override
   public Comparator<T> comparator() {
      return comparator;
   }

   @Override
   public SortedSet<T> subSet(T t, T t1) {
      if (isEmpty()) {
         return null;
      }
      OrderedSet<T> result = new OrderedSetImpl<T>();
      for (int i = indexOf(t); i <= indexOf(t1); i++) {
         result.add(getAt(i));
      }
      return result;
   }

   @Override
   public SortedSet<T> headSet(T t) {
      if (isEmpty()) {
         return null;
      }
      return subSet(getAt(0), t);
   }

   @Override
   public SortedSet<T> tailSet(T t) {
      if (isEmpty()) {
         return null;
      }
      return subSet(t, getAt(size() - 1));
   }

   @Override
   public T first() {
      if (isEmpty()) {
         return null;
      }
      return elements.get(0);
   }

   @Override
   public T last() {
      if (isEmpty()) {
         return null;
      }
      return elements.get(size() - 1);
   }

   @Override
   public String toString() {
      String result = "{";
      for (int i = 0; i < size() - 1; i++) {
         result += getAt(i).toString() + ", ";
      }
      return result + (size() > 0 ? getAt(size() - 1) : "") + "}";
   }

   private class OrderedSetIteratorImpl implements Iterator<T> {
      private int position;
      private int increment;

      OrderedSetIteratorImpl() {
         if (isAscending) {
            position = -1;
            increment = 1;
         }
         else {
            position = size();
            increment = -1;
         }
      }

      @Override
      public boolean hasNext() {
         return ((position + increment) >= 0 && (position + increment) < size());
      }

      @Override
      public T next() {
         position += increment;
         return elements.get(position);
      }

      @Override
      public void remove() {
         throw new UnsupportedOperationException("This operation is not supported.");
      }
   }

   private class PositionComparator implements Comparator<T> {
      @Override
      public int compare(T t, T t1) {
         int tIdx = indexOf(t);
         int t1Idx = indexOf(t1);
         if (t1Idx < 0 && t1Idx < 0) {
            throw new IllegalArgumentException("Could not compare these items: " + t + ", " + t1);
         }
         else {
            return t1Idx - tIdx;
         }
      }
   }
}
